In this paper, we examine the basic properties of n-th order linear feedback shift registers and show that n-th order shift registers based discrete logarithm problem is equivalent to discrete logarithm problem. This shows that the algebraic structure of n-th order linear feedback shift registers is useful in constructing cryptographic primitives.

It is shown that the effective secret-key size of TOYOCRYPT-HS1 stream cipher is only 96 bits, although the secret key consists of 128 bits. This characteristic opens a door for developing an algorithm for cryptanalysis based on the time-memory-data trade-off with the overall complexity significantly smaller than the exhaustive search over the effective key space.

In this paper, we propose a new digital signature scheme based on a third order linear feedback shift register for signing documents. This signature scheme is different from most of the signature schemes that are based on discrete logarithm problem, elliptic curves discrete logarithm problem, RSA or quadratic residues. An efficient algorithm for computing kth term of a sequence is also presented. The advantage of this scheme is that the computation is efficient than Schnorr scheme. We also show that the security of the proposed signature scheme is equivalent to that of Schnorr signature scheme.

An algorithm for cryptanalysis of certain keystream generators is proposed. The developed algorithm has the following two advantages over other reported ones: it is more powerful, and it can be implemented by a high-speed software or a simple hardware suitable for high parallel architectures. The algorithm is based on error-correction of information bits only (of the corresponding binary block code) with a novel method for construction of the parity-checks, and the employed error-correction procedure is an APP based threshold decoding. Experimental and theoretical analyses of the algorithm performance are presented, and its complexity is evaluated. The proposed algorithm is compared with recently proposed improved fast correlation attacks based on convolutional codes and turbo decoding. The underlying principles, performance and complexity are compared, and the gain obtained with the novel approach is pointed out.

A compact new test structure using shift register circuits for extracting components of the capacitance matrix of the multi-layer interconnections has been proposed. An extraction method of the capacitance matrix is also presented. As a result of fabrication, capacitance values obtained by measurement are in good agreement with the numerical calculation. We also showed an estimation method of the measurement errors.

This paper presents a new architecture for multiple-input signature analyzers. The proposed signature analyzer with Hδ inputs is designed by parallelizing a GLFSR(δ,m), where δ is the number of input signals and m is the number of stages in the feedback shift register. The GLFSR, developed by Pradhan and Gupta, is a general framework for representing LFSR-based signature analyzers. The parallelization technique described in this paper can be applied to any kind of GLFSR signature analyzer, e. g. , SISRs, MISRs, multiple MISRs and MLFSRs. It is shown that a proposed signature analyzer with Hδ inputs requires less complex hardware than either single GLFSR(Hδ,m)s or a parallel construction of the H original GLFSR(δ,m)s. It is also shown that the proposed signature analyzer, while requiring simpler hardware, has comparable aliasing probability with analyzers using conventional GLFSRs for some CUT error models of the same test response length and test time. The proposed technique would be practical for testing CUTs with a large number of output sequences, since the test circuit occupies a smaller area on the LSI chip than the conventional multiple-input signature analyzers of comparable aliasing probability.

In this paper, we develop parallel scrambling techniques for the distributed sample scrambling (DSS), which are directly applicable to the bit- and multibit-interleaved multiplexing environments. We first consider how to realize PSRGs, parallel samplings and parallel corrections for the multibit-parallel DSS (MPDSS), which are the fundamental problems in realizing the MPDSS scramblers and descramblers. The results are summarized in three sets of theorems, and a corollary is attached to each theorem to specifically handle the case of the parallel DSS (PDSS). The theorems and corollaries are supported by examples that demonstrate the relevant MPDSS scramblers and descramblers.

In this paper, a construction of de Bruijn sequences using maximum length linear sequences is considered. The construction is based on the well-known cross-join (CJ) method: Maximum length linear sequences are used to produce de Bruijn sequences by the CJ process. Properties of the CJ paris in the maximum length linear sequences are investigated. It is conjectured that the number of CJ pairs in a maximum length linear sequence is given by (22n-3+1)/3-2n-2, where n2 is the length of the linear feedback shift register with the sequence. The CJ paris for some special cases are obtained. An algorithm for finding CJ pairs is described and a method of implementation is discussed briefly.